package com.my.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Created by ZhongGang
 * at 2018/10/8 14:52
 * <p>
 * 选择排序
 * 1. 遍历数组元素，找到最小元素的索引
 * 2. 与数组的第一个位置交换元素
 * 3. 遍历余下数组元素，重复步骤1，2
 * <p>
 * 算法复杂度 N的平方
 */
public class SelectionSorter<T extends Comparable<T>> implements Sortable<T> {
    private static final Logger LOGGER = LoggerFactory.getLogger(SelectionSorter.class);

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length <= 1) {
            return elements;
        }

        int length = elements.length;
        for (int i = 0; i < length; i++) {
            int min = i;
            for (int j = i + 1; j < length; j++) {
                if (elements[j].compareTo(elements[min]) < 0) {
                    min = j;
                }
                LOGGER.info("i: {}, j: {}, min: {}, elements: {}", i, j, min, elements);
            }

            T tmp = elements[i];
            elements[i] = elements[min];
            elements[min] = tmp;
        }

        return elements;
    }
}
